package aer.PrimoDeRiesgo;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class PrimoDeRiesgo {
	
	private static int numero, l, i, x, k;
	private static String linea;
	private static boolean primo;
	private static BufferedReader br = new BufferedReader(
			new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		int casos = Integer.parseInt(br.readLine());
		for (int j = 0; j < casos; j++) {
			programa();
		}
	}

	private static void programa() throws Exception {
		linea = br.readLine();
		contar();
		numero--;

		while (!esPrimo(numero)) {
			numero--;
		}

		System.out.print(numero + "\n");
	}

	private static boolean esPrimo(int n) {
		if (n < 1) {
			primo = false;
		} else if (n == 2 || n == 1) {
			primo = true;
		} else if (n % 2 == 0) {
			primo = false;
		} else {
			primo = true;
			k = 3;
			while (k <= Math.sqrt(n) && primo) {
				if (n % k == 0) {
					primo = false;
				}
				k += 2;
			}
		}
		return primo;
	}

	private static void contar() {
		l = linea.length();
		numero = 0;

		for (i = 0; i < l; i++) {
			x = linea.charAt(i);
			numero += x;
		}
	}

}